Divide-and-conquer is patterned after the brilliant strategy employed by the French emperor Napoleon in the Battle of Austerlitz on December 2, 1805. A combined army of Austrians and Russians outnumbered Napoleon’s army by about 15,000 soldiers. The Austro-Russian army launched a massive attack against the French right flank. Anticipating their attack, Napoleon drove against their center and split their forces in two. Because the two smaller armies were individually no match for Napoleon, they each suffered heavy losses and were compelled to retreat. By dividing the large army into two smaller armies and individually conquering these two smaller armies, Napoleon was able to conquer the large army.

분할정복법은 Austerlitz 전투에서 나폴레옹이 고안한 전략을 모방한 것이다. 프랑스군은 오스트리아와 러시아 연합군에 비해 수적으로 열세였지만, 나폴레옹이 적 중앙을 돌파하여 적의 부대를 둘로 나누고 각개격파함으로써 전쟁에서 승리할 수 있었다.

The Divide-and-Conquer Approach

It divides an instance of a problem into two or more smaller instances. The smaller instances are usually instances of the original problem. If solutions to the smaller instances can be obtained readily, the solution to the original instance can be obtained by combining these solutions. If the smaller instances are still too large to be solved readily, they can be divided into still smaller instances. This process of dividing the instances continues until they are so small that a solution is readily obtainable.

1. Divide

문제를 해결하기 쉽도록 여러개의 작은 부분으로 나눈다. 이 작은 문제들은 원래 문제의 한 부분이다.

2. Conquer - Solve

나눈 문제를 각각 해결한다. 만약 문제가 여전히 커서 쉽게 해결되지 않으면 더 작은 부분으로 나눈다.

3. Combine - Obtain the solution

필요하다면 해결된 해답을 모은다.

The divide-and-conquer approach is a top-down approach.

분할정복법은 top-down 방식으로 문제를 접근/해결한다.